package com.zp.self.module.level_4_算法练习.数据结构.二叉树.平衡二叉树;

import com.zp.self.module.level_4_算法练习.算法.排序.猴子排序_量子级别;
import org.junit.Test;

import java.util.HashMap;
import java.util.Map;


/**
 * @author ：by Zeng Peng
 * @date ：Created 2022/6/2 22:07
 * @description ：删除某个节点
 */
public class 平衡二叉树_删除 {

    @Test
    public  void testDeleteAVL(){
        int[] arr = new int[]{ 1, 4, 5, 6, 7, 10, 9, 8, 23, 2, 13, 32, 321, 32, 321, 312, 321, 1, 1, 1, 1, 1, 1, 1, 2, 1, 2, 3, 23, 2 };
        AvlNode node = 平衡二叉树_插入_构建.buildAVL(arr);
        //删除平衡二叉树
        猴子排序_量子级别.shuffle(arr);
        Map<AvlNode,Integer> map = new HashMap<>();
        for (int num : arr) {
            node=deleteAVL(node,num);
            map.clear();
            System.out.println("删除:"+ num +"后,是否还是AVL: "+平衡二叉树_验证.isAVL(node,map));
        }
        System.out.println(node);
    }

    /**
     题目：编写方法：将平衡二叉树中的某个节点删除

     分析：
         1.找到要删除的节点deleteNode -- 不存在：则返回    --时间：O(logn)
                                         存在：并找到左子树最大值leftMaxNode，如果没有，则用自己代替
         2.从根节点向下寻找向上递归找到 leftMaxNode：      --时间：O(logn)
                                        leftMaxNode > node 向右子树递归
                                        leftMaxNode < node 向左子树递归
                                        leftMaxNode = node 找到了要删除的节点，节点可能有左节点，so返回node.left --73行
                        上层节点，根据情况指向返回值。
                        上层节点的子节点高度可能发生变化 -- 进行平衡调整、更新节点自己的高度

     边界值 & 注意点：
        1.
     **/
    public static AvlNode deleteAVL(AvlNode node,int data){
        //1.查找data
        AvlNode delNode = 平衡二叉树_查找.search(node, data);
        if(delNode==null)
            return node;
        //2.查找左子树中的最大值节点
        AvlNode leftMaxNode = searchLeftMaxNode(delNode.lchild);
        if(leftMaxNode==null)//左子树节点都为空
            leftMaxNode = delNode;
        //3.从顶层开始寻找需要删除的节点leftMaxNode节点，弹栈时，保证节点平衡
        node =  deleteBalance(node,leftMaxNode);
        //4.将自己值 替换为 被删除的值
        delNode.data = leftMaxNode.data;
        return node;
    }
    //Description: 找到删除节点，并删除、再平衡 O(logn)
    private static AvlNode deleteBalance(AvlNode proNode, AvlNode deleteNode) {
        if (deleteNode.data>proNode.data){//删除节点在右边
            proNode.rchild = deleteBalance(proNode.rchild,deleteNode);
        }else if(deleteNode.data<proNode.data){//删除节点在左边
            proNode.lchild = deleteBalance(proNode.lchild,deleteNode);
        }else{//这里有相同的值
            if (proNode.lchild!=null && proNode.lchild.data==deleteNode.data) //这里好麻烦哦 -- 要判断是否是相同堆节点
                proNode.lchild = deleteBalance(proNode.lchild,deleteNode);
            else
                return proNode.rchild;
        }
        proNode = balanceAvlNode(proNode);
        proNode.height = Math.max(平衡二叉树_插入_构建.height(proNode.lchild), 平衡二叉树_插入_构建.height(proNode.rchild)) + 1;
        return  proNode;
    }

    //平衡当前节点
    private static AvlNode balanceAvlNode(AvlNode proNode) {
        int balanceFactor = getBalanceFactor(proNode);
        if (balanceFactor == 2) {//左边高
            if(getBalanceFactor(proNode.lchild) == -1){
                proNode = 平衡二叉树_插入_构建.L_R_Rotate(proNode);//左右：左右
            }else {
                proNode = 平衡二叉树_插入_构建.R_Rotate(proNode);//左左：优选
            }
        }else if(balanceFactor == -2){//右边高
            if(getBalanceFactor(proNode.rchild)==1){
                proNode = 平衡二叉树_插入_构建.R_L_Rotate(proNode);//右左 :右左
            }else {
                proNode = 平衡二叉树_插入_构建.L_Rotate(proNode);//右右：左旋
            }
        }
        return proNode;
    }

    public static int getBalanceFactor(AvlNode node){
        return 平衡二叉树_插入_构建.height(node.lchild) - 平衡二叉树_插入_构建.height(node.rchild);
    }
    //Description: 查找左子树最大值 O(logn)
    public static AvlNode searchLeftMaxNode(AvlNode lchild) {
        if(lchild==null)
            return null;
        while (lchild.rchild!=null)
            lchild = lchild.rchild;
        return lchild;
    }
}
